//给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。 
//
// 如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如： 
//
// 
// 数字 4 是 特殊数字，因为它的真因数为 1 和 2。 
// 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。 
// 
//
// 返回区间 [l, r] 内 不是 特殊数字 的数字数量。 
//
// 
//
// 示例 1： 
//
// 
// 输入： l = 5, r = 7 
// 
//
// 输出： 3 
//
// 解释： 
//
// 区间 [5, 7] 内不存在特殊数字。 
//
// 示例 2： 
//
// 
// 输入： l = 4, r = 16 
// 
//
// 输出： 11 
//
// 解释： 
//
// 区间 [4, 16] 内的特殊数字为 4 和 9。 
//
// 
//
// 提示： 
//
// 
// 1 <= l <= r <= 10⁹ 
// 
//
// Related Topics 数组 数学 数论 👍 34 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2024-11-22 18:58:54
 * @description 3233.统计不是特殊数字的数字数量
 
 */
 
public class FindTheCountOfNumbersWhichAreNotSpecial {
    public static void main(String[] args) {
    //测试代码
    FindTheCountOfNumbersWhichAreNotSpecial fun = new FindTheCountOfNumbersWhichAreNotSpecial();
    Solution solution= fun.new Solution();
    System.out.println(solution.nonSpecialCount(4, 16));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //太朴素了，直接超时
    public int nonSpecialCount1(int l, int r) {
        int res=0;
        for (int i = l; i <=r ; i++) {
            if(countSpecialNumbers(i)!=2) res++;
        }
        return res;
    }
    //计算因数数量
    public int countSpecialNumbers(int n) {
        int res=0;
        for (int i = 1; i<=n/2; i++) {
            if(n%i==0) res+=1;
            if(res>2) return res;
        }
        return res;
    }
    /*
    *只有质数的平方才可能是特殊数，
    * 其他的数，1和质数只有一个真因素
    * 不是1也不是质数也不是质数的平方，至少有三个真因数
    * 所以原问题等价于求
    * 0到根号r和0到根号l的质数的个数，之差
    * 用总数减去特殊数就是答案
    * sqrt 10^9 =31622
    * */


    public int nonSpecialCount(int l, int r) {
           int MX = 31622;
           int[] PI = new int[MX + 1];
            for (int i = 2; i <= MX; i++) {
                if (PI[i] == 0) { // i 是质数
                    PI[i] = PI[i - 1] + 1;
                    //因为i*i以前的数，一定都被前面比i小的数标记过了，所以直接从i*i开始
                    for (int j = i * i; j <= MX; j += i) { // 注：如果 MX 比较大，小心 i*i 溢出
                        PI[j] = -1; // 标记 i 的倍数为合数
                    }
                } else {
                    PI[i] = PI[i - 1];
                }
            }
        return r - l + 1 - (PI[(int) Math.sqrt(r)] - PI[(int) Math.sqrt(l - 1)]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
